package leetcode._08_dynic;

import org.junit.Test;

/**
 * @author pppppp
 * @date 2022/3/25 16:46
 * 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
 * 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
 * 假设每一种面额的硬币有无限个。 
 * 题目数据保证结果符合 32 位带符号整数。
 *  
 * 示例 1：
 * 输入：amount = 5, coins = [1, 2, 5]
 * 输出：4
 * 解释：有四种方式可以凑成总金额：
 * 5=5
 * 5=2+2+1
 * 5=2+1+1+1
 * 5=1+1+1+1+1
 * <p>
 * 示例 2：
 * 输入：amount = 3, coins = [2]
 * 输出：0
 * 解释：只用面额 2 的硬币不能凑成总金额 3 。
 * <p>
 * 示例 3：
 * 输入：amount = 10, coins = [10]
 * 输出：1
 *  
 * 提示：
 * 1 <= coins.length <= 300
 * 1 <= coins[i] <= 5000
 * coins 中的所有值 互不相同
 * 0 <= amount <= 5000
 */
public class _518_零钱兑换II {

    @Test
    public void T_0() {
        int[][] coins = {{2,5},{1, 2, 5}, {2}, {10}};
        int[] amount = {5,5, 3, 10};
        int[] ans = {1,4, 0, 1};
        for (int i = 1; i < coins.length; i++) {
            // System.out.println(change_0(amount[i], coins[i]) == ans[i]);
            // System.out.println(change_1(amount[i], coins[i]) == ans[i]);
            System.out.println(change_review(amount[i], coins[i]) == ans[i]);
        }
    }

    /*review:完全背包 dp[i][j] = dp[i-1][j] + dp[i][j-Ci]*/
    public int change_review(int amount, int[] coins) {
        int[][] dp = new int[coins.length][amount + 1];
        // dp[0][0] = 1;
        for (int i = 0; i <= amount; i++) {
            dp[0][i] = i % coins[0] == 0 ? 1:0;
        }
        for (int i = 1; i < coins.length; i++) {
            for (int j = 0; j <= amount; j++) {
                if(j >= coins[i]){
                    dp[i][j] = dp[i][j-coins[i]] + dp[i-1][j];
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[coins.length-1][amount];
    }
    /*1.官方的优化题解：完全背包  外层遍历coin 内层遍历 amount
    dp[i] 凑成 i的种类数量
    对于每一个 dp[i] 若能加入一个 coin 面值的数字 则进行累加*/

    public int change_1(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i-coin];
            }
        }
        return dp[amount];
    }


    /*0.利用前i-1 递推————3层for循环，dp[i][j] = Σdp[i-1][j - k*Ci]*/
    public int change_0(int amount, int[] coins) {
        int[][] dp = new int[coins.length][amount + 1];
        for (int i = 0; i <= amount; i++) {
            dp[0][i] = i % coins[0] == 0 ? 1 : 0;
        }

        for (int i = 1; i < coins.length; i++) {
            for (int j = 0; j <= amount; j++) {
                for (int k = 0; j - k* coins[i] >= 0 ; k++) {
                    dp[i][j] += dp[i-1][j- k*coins[i]];
                }
            }
        }
        return dp[coins.length-1][amount];
    }
}
